#include<bits/stdc++.h>
using namespace std;
string s;
const int N=1e5+3; 
int n,x;
bool check(int k){
	priority_queue<int>q;
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(s[i]!=s[i-1]){
			q.push(cnt);
			cnt=0;
		}
		cnt++;
	}
	q.push(cnt); 
	int res=0;
	while(q.top()>k){
		res++;
		
		int t=q.top();q.pop();
		q.push(t/2);
		q.push(t/2);
	}
	return res<=x;
}
void solve(){
	cin>>n>>x;
	cin>>s;
	s='4'+s;
	int l=1,r=n;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	} 
	cout<<r<<endl;
}
int main(){
	int t;cin>>t;
	while(t--)
	solve();
	return 0; 
}
